{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-03T08:13:16.182629Z",
     "start_time": "2018-09-03T08:13:16.176613Z"
    },
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "from math import inf\n",
    "from itertools import product\n",
    " \n",
    "def floyd_warshall(n, edge):\n",
    "    rn = range(n)\n",
    "    dist = [[inf] * n for i in rn]\n",
    "    nxt  = [[0]   * n for i in rn]\n",
    "    for i in rn:\n",
    "        dist[i][i] = 0\n",
    "    for u, v, w in edge:\n",
    "        dist[u-1][v-1] = w\n",
    "        nxt[u-1][v-1] = v-1\n",
    "    for k, i, j in product(rn, repeat=3):\n",
    "        sum_ik_kj = dist[i][k] + dist[k][j]\n",
    "        if dist[i][j] > sum_ik_kj:\n",
    "            dist[i][j] = sum_ik_kj\n",
    "            nxt[i][j]  = nxt[i][k]\n",
    "    print(\"pair     dist    path\")\n",
    "    for i, j in product(rn, repeat=2):\n",
    "        if i != j:\n",
    "            path = [i]\n",
    "            while path[-1] != j:\n",
    "                path.append(nxt[path[-1]][j])\n",
    "            print(\"%d → %d  %4d       %s\" \n",
    "                  % (i + 1, j + 1, dist[i][j], \n",
    "                     ' → '.join(str(p + 1) for p in path)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-03T08:13:16.580335Z",
     "start_time": "2018-09-03T08:13:16.577329Z"
    }
   },
   "outputs": [],
   "source": [
    "n=3\n",
    "edge = [[1, 2, 5],[2, 3, 30],[3, 1, 35],[1,3,-35]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-03T08:13:17.067186Z",
     "start_time": "2018-09-03T08:13:17.064176Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pair     dist    path\n",
      "1 → 2     5       1 → 2\n",
      "1 → 3   -35       1 → 3\n",
      "2 → 1    65       2 → 3 → 1\n",
      "2 → 3    30       2 → 3\n",
      "3 → 1    35       3 → 1\n",
      "3 → 2    40       3 → 1 → 2\n"
     ]
    }
   ],
   "source": [
    "floyd_warshall(n, edge)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-03T08:15:07.003766Z",
     "start_time": "2018-09-03T08:15:07.000760Z"
    }
   },
   "outputs": [],
   "source": [
    "for u, v, w in edge:\n",
    "    dist[u-1][v-1] = w\n",
    "    nxt[u-1][v-1] = v-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-03T06:39:26.767854Z",
     "start_time": "2018-09-03T06:39:26.763843Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pair     dist    path\n",
      "1 → 2    -1       1 → 3 → 4 → 2\n",
      "1 → 3    -2       1 → 3\n",
      "1 → 4     0       1 → 3 → 4\n",
      "2 → 1     4       2 → 1\n",
      "2 → 3     2       2 → 1 → 3\n",
      "2 → 4     4       2 → 1 → 3 → 4\n",
      "3 → 1     5       3 → 4 → 2 → 1\n",
      "3 → 2     1       3 → 4 → 2\n",
      "3 → 4     2       3 → 4\n",
      "4 → 1     3       4 → 2 → 1\n",
      "4 → 2    -1       4 → 2\n",
      "4 → 3     1       4 → 2 → 1 → 3\n"
     ]
    }
   ],
   "source": [
    "floyd_warshall(4, [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-03T06:40:51.133248Z",
     "start_time": "2018-09-03T06:40:51.126731Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, inf, -2, inf], [4, 0, 2, inf], [inf, inf, 0, 2], [inf, -1, inf, 0]]\n",
      "[[0, 0, 2, 0], [0, 0, 0, 0], [0, 0, 0, 3], [0, 1, 0, 0]]\n",
      "[[0, inf, -2, inf], [4, 0, 2, inf], [inf, inf, 0, 2], [3, -1, inf, 0]]\n",
      "[[0, 0, 2, 0], [0, 0, 0, 0], [0, 0, 0, 3], [1, 1, 0, 0]]\n",
      "[[0, inf, -2, inf], [4, 0, 2, inf], [inf, inf, 0, 2], [3, -1, 1, 0]]\n",
      "[[0, 0, 2, 0], [0, 0, 0, 0], [0, 0, 0, 3], [1, 1, 1, 0]]\n",
      "[[0, inf, -2, 0], [4, 0, 2, inf], [inf, inf, 0, 2], [3, -1, 1, 0]]\n",
      "[[0, 0, 2, 2], [0, 0, 0, 0], [0, 0, 0, 3], [1, 1, 1, 0]]\n",
      "[[0, inf, -2, 0], [4, 0, 2, 4], [inf, inf, 0, 2], [3, -1, 1, 0]]\n",
      "[[0, 0, 2, 2], [0, 0, 0, 0], [0, 0, 0, 3], [1, 1, 1, 0]]\n",
      "[[0, -1, -2, 0], [4, 0, 2, 4], [inf, inf, 0, 2], [3, -1, 1, 0]]\n",
      "[[0, 2, 2, 2], [0, 0, 0, 0], [0, 0, 0, 3], [1, 1, 1, 0]]\n",
      "[[0, -1, -2, 0], [4, 0, 2, 4], [5, inf, 0, 2], [3, -1, 1, 0]]\n",
      "[[0, 2, 2, 2], [0, 0, 0, 0], [3, 0, 0, 3], [1, 1, 1, 0]]\n",
      "[[0, -1, -2, 0], [4, 0, 2, 4], [5, 1, 0, 2], [3, -1, 1, 0]]\n",
      "[[0, 2, 2, 2], [0, 0, 0, 0], [3, 3, 0, 3], [1, 1, 1, 0]]\n"
     ]
    }
   ],
   "source": [
    "n=4\n",
    "edge = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]]\n",
    "\n",
    "rn = range(n)\n",
    "dist = [[inf] * n for i in rn]\n",
    "nxt  = [[0]   * n for i in rn]\n",
    "for i in rn:\n",
    "    dist[i][i] = 0\n",
    "for u, v, w in edge:\n",
    "    dist[u-1][v-1] = w\n",
    "    nxt[u-1][v-1] = v-1\n",
    "\n",
    "for k, i, j in product(rn, repeat=3):\n",
    "    sum_ik_kj = dist[i][k] + dist[k][j]\n",
    "    if dist[i][j] > sum_ik_kj:\n",
    "        dist[i][j] = sum_ik_kj\n",
    "        nxt[i][j]  = nxt[i][k]\n",
    "        print(dist)\n",
    "        print(nxt)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-03T06:40:52.643764Z",
     "start_time": "2018-09-03T06:40:52.638752Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pair     dist    path\n",
      "1 → 2    -1       1 → 3 → 4 → 2\n",
      "1 → 3    -2       1 → 3\n",
      "1 → 4     0       1 → 3 → 4\n",
      "2 → 1     4       2 → 1\n",
      "2 → 3     2       2 → 1 → 3\n",
      "2 → 4     4       2 → 1 → 3 → 4\n",
      "3 → 1     5       3 → 4 → 2 → 1\n",
      "3 → 2     1       3 → 4 → 2\n",
      "3 → 4     2       3 → 4\n",
      "4 → 1     3       4 → 2 → 1\n",
      "4 → 2    -1       4 → 2\n",
      "4 → 3     1       4 → 2 → 1 → 3\n"
     ]
    }
   ],
   "source": [
    "\n",
    "print(\"pair     dist    path\")\n",
    "for i, j in product(rn, repeat=2):\n",
    "    if i != j:\n",
    "        path = [i]\n",
    "        while path[-1] != j:\n",
    "            path.append(nxt[path[-1]][j])\n",
    "        print(\"%d → %d  %4d       %s\" \n",
    "              % (i + 1, j + 1, dist[i][j], \n",
    "                 ' → '.join(str(p + 1) for p in path)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-03T07:58:19.463242Z",
     "start_time": "2018-09-03T07:58:14.642Z"
    }
   },
   "outputs": [],
   "source": [
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "\"\"\"\n",
    "Created on Thu Jul 13 14:56:37 2017\n",
    "@author: linzr\n",
    "\"\"\"\n",
    " \n",
    "## 表示无穷大\n",
    "INF_val = 9999\n",
    " \n",
    "class Floyd_Path():\n",
    "    def __init__(self, node, node_map, path_map):\n",
    "        self.node = node\n",
    "        self.node_map = node_map\n",
    "        self.node_length = len(node_map)\n",
    "        self.path_map = path_map\n",
    "        self._init_Floyd()\n",
    "    \n",
    "    def __call__(self, from_node, to_node):\n",
    "        self.from_node = from_node\n",
    "        self.to_node = to_node\n",
    "        return self._format_path()\n",
    " \n",
    "    def _init_Floyd(self):\n",
    "        for k in range(self.node_length):\n",
    "            for i in range(self.node_length):\n",
    "                for j in range(self.node_length):\n",
    "                    tmp = self.node_map[i][k] + self.node_map[k][j]\n",
    "                    if self.node_map[i][j] > tmp:\n",
    "                        self.node_map[i][j] = tmp\n",
    "                        self.path_map[i][j] = self.path_map[i][k]\n",
    "                        \n",
    "        print ('_init_Floyd is end')\n",
    " \n",
    " \n",
    "    def _format_path(self):\n",
    "        node_list = []\n",
    "        temp_node = self.from_node\n",
    "        obj_node = self.to_node\n",
    "        print((\"the shortest path is: %d\")%(self.node_map[temp_node][obj_node]))\n",
    "        node_list.append(self.node[temp_node])\n",
    "        while True:\n",
    "            node_list.append(self.node[self.path_map[temp_node][obj_node]])\n",
    "            temp_node = self.path_map[temp_node][obj_node]\n",
    "            if temp_node == obj_node:\n",
    "                break;\n",
    "        \n",
    "        return node_list\n",
    "                \n",
    " \n",
    "        \n",
    " \n",
    " \n",
    "def set_node_map(node_map, node, node_list, path_map):\n",
    "    for i in range(len(node)):\n",
    "        ## 对角线为0\n",
    "        node_map[i][i] = 0\n",
    "    for x, y, val in node_list:\n",
    "        node_map[node.index(x)][node.index(y)] = node_map[node.index(y)][node.index(x)] = val\n",
    "        path_map[node.index(x)][node.index(y)] = node.index(y)\n",
    "        path_map[node.index(y)][node.index(x)] = node.index(x)\n",
    " \n",
    "    \n",
    "if __name__ == \"__main__\":\n",
    "    node = ['A', 'B', 'C', 'D', 'E', 'F', 'G']\n",
    "    node_list = [('A', 'F', 9), ('A', 'B', 10), ('A', 'G', 15), ('B', 'F', 2),\n",
    "                 ('G', 'F', 3), ('G', 'E', 12), ('G', 'C', 10), ('C', 'E', 1),\n",
    "                 ('E', 'D', 7)]\n",
    "  \n",
    "    ## node_map[i][j] 存储i到j的最短距离\n",
    "    node_map = [[INF_val for val in range(len(node))] for val in range(len(node))]\n",
    "    ## path_map[i][j]=j 表示i到j的最短路径是经过顶点j\n",
    "    path_map = [[INF_val for val in range(len(node))] for val in range(len(node))]\n",
    "    \n",
    "    ## set node_map\n",
    "    set_node_map(node_map, node, node_list, path_map)\n",
    " \n",
    " \n",
    "    ## select one node to obj node, e.g. A --> D(node[0] --> node[3])\n",
    "    from_node = node.index('A')\n",
    "    to_node = node.index('E')\n",
    "    Floydpath = Floyd_Path(node, node_map, path_map)\n",
    "    path = Floydpath(from_node, to_node)\n",
    "    print (path)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-03T07:58:47.056782Z",
     "start_time": "2018-09-03T07:58:46.027098Z"
    }
   },
   "outputs": [],
   "source": [
    "## 表示无穷大\n",
    "INF_val = 9999\n",
    " \n",
    "class Floyd_Path():\n",
    "    def __init__(self, node, node_map, path_map):\n",
    "        self.node = node\n",
    "        self.node_map = node_map\n",
    "        self.node_length = len(node_map)\n",
    "        self.path_map = path_map\n",
    "        self._init_Floyd()\n",
    "    \n",
    "    def __call__(self, from_node, to_node):\n",
    "        self.from_node = from_node\n",
    "        self.to_node = to_node\n",
    "        return self._format_path()\n",
    " \n",
    "    def _init_Floyd(self):\n",
    "        for k in range(self.node_length):\n",
    "            for i in range(self.node_length):\n",
    "                for j in range(self.node_length):\n",
    "                    tmp = self.node_map[i][k] + self.node_map[k][j]\n",
    "                    if self.node_map[i][j] > tmp:\n",
    "                        self.node_map[i][j] = tmp\n",
    "                        self.path_map[i][j] = self.path_map[i][k]\n",
    "                        \n",
    "        print ('_init_Floyd is end')\n",
    " \n",
    " \n",
    "    def _format_path(self):\n",
    "        node_list = []\n",
    "        temp_node = self.from_node\n",
    "        obj_node = self.to_node\n",
    "        print((\"the shortest path is: %d\")%(self.node_map[temp_node][obj_node]))\n",
    "        node_list.append(self.node[temp_node])\n",
    "        while True:\n",
    "            node_list.append(self.node[self.path_map[temp_node][obj_node]])\n",
    "            temp_node = self.path_map[temp_node][obj_node]\n",
    "            if temp_node == obj_node:\n",
    "                break;\n",
    "        \n",
    "        return node_list\n",
    "                \n",
    " \n",
    "        \n",
    " \n",
    " \n",
    "def set_node_map(node_map, node, node_list, path_map):\n",
    "    for i in range(len(node)):\n",
    "        ## 对角线为0\n",
    "        node_map[i][i] = 0\n",
    "    for x, y, val in node_list:\n",
    "        node_map[node.index(x)][node.index(y)] = node_map[node.index(y)][node.index(x)] = val\n",
    "        path_map[node.index(x)][node.index(y)] = node.index(y)\n",
    "        path_map[node.index(y)][node.index(x)] = node.index(x)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-09-03T07:58:47.114937Z",
     "start_time": "2018-09-03T07:58:47.105913Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "_init_Floyd is end\n",
      "the shortest path is: 0\n",
      "['A', 'C']\n"
     ]
    }
   ],
   "source": [
    "\n",
    "node = ['A', 'B', 'C']\n",
    "node_list = [('A', 'B', 0.95), ('A', 'C', 0.65), ('B', 'C', 0.7)]\n",
    "\n",
    "## node_map[i][j] 存储i到j的最短距离\n",
    "node_map = [[INF_val for val in range(len(node))] for val in range(len(node))]\n",
    "## path_map[i][j]=j 表示i到j的最短路径是经过顶点j\n",
    "path_map = [[0 for val in range(len(node))] for val in range(len(node))]\n",
    "\n",
    "## set node_map\n",
    "set_node_map(node_map, node, node_list, path_map)\n",
    "\n",
    "\n",
    "## select one node to obj node, e.g. A --> D(node[0] --> node[3])\n",
    "from_node = node.index('A')\n",
    "to_node = node.index('C')\n",
    "Floydpath = Floyd_Path(node, node_map, path_map)\n",
    "path = Floydpath(from_node, to_node)\n",
    "print (path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
